A typical FPGA comprises a large plurality of configurable logic blocks (CLBs) surrounded by input-output blocks and interconnectable through a routing structure. The first FPGA is described by Ross Freeman in U.S. reissue patent Re 34,363, and is incorporated herein by reference. The CLBs and routing structure of the FPGA are arranged in an array or in a plurality of sub-arrays wherein respective CLBs and associated portions of the routing structure are placed edge to edge in what is commonly referred to as a tiled arrangement. Such a tiled arrangement is described by Danesh Tavana et al. in U.S. patent application Ser. No. 08/618,445, and that application is also incorporated herein by reference. The CLB portion of a tile comprises a plurality of primitive cells which may be interconnected in a variety of ways to perform a desired logic function. For example, a CLB may comprise a plurality of lookup tables (LUTs), multiplexers and registers. As used herein, the term "primitive cell" means the lowest level of user accessible component.
When an FPGA comprises thousands of CLBs in large arrays of tiles, the task of establishing the required multitude of interconnections between primitive cells inside a CLB and between the CLBs becomes so onerous that it requires software tool implementation. Accordingly, the manufacturers of FPGAs including the assignee hereof, Xilinx, Inc., have developed place and route software tools which may be used by their customers to implement their respective designs. Place and route tools not only provide the means of implementing users' designs, but can also provide an accurate and final analysis of static timing and dynamic power consumption for an implemented design scheme. In fact, better place and route software provides iterative processes to minimize timing and power consumption as a final design implementation is approached. Iterative steps are usually necessary to reach a final design primarily because of the unknown impact of the placement step on routing resources (wires and connectors) available to interconnect the logic of a user's design. Iterative place and route procedures can be time consuming. A typical design implementation procedure can take many hours of computer time using conventional place and route software tools. Thus, there is an ongoing need to provide a method for reducing design implementation time by increasing the accuracy of static timing and dynamic power analysis during computer-aided design procedures for FPGAs.
Another challenge for software tools used to place a user's design into a coarse-grained FPGA is to make optimum use of the features other than lookup tables and registers that are available in the FPGA architecture. These can include fast carry chains, XOR gates for generating sums, multiplexers for generating five-input functions, and possibly other features available in the architecture. In order to achieve maximum density and maximum performance of user logic in an FPGA, the software must make use of these dedicated features where possible. Thus, there is also a need to densely pack the user's design into the architecture that will implement the design.